package com.logbug.algorithm;

import java.util.Arrays;

public class Test {
    static int[] getArr(){
        return new int[]{2, 3, 1, 3, 6, 7, 3, 6, 7, 4};
    }
    public static void main(String[] args) {
        int[] arr = getArr();
        QuickSort sorter = new QuickSort(arr);
        sorter.sort();
        System.out.println("quick sort: \t"+Arrays.toString(arr));

        int[] arr2=getArr();
        MergeSort mergeSort=new MergeSort(arr2);
        mergeSort.sort();
        System.out.println("merge sort: \t"+Arrays.toString(arr2));

        int[] arr3=getArr();
        BubbleSort.sort(arr3);
        System.out.println("bubble sort: \t"+Arrays.toString(arr3));

        System.out.println("n=10 fib: \t" + Fib.fib(10));
        System.out.println("n=10 fib2: \t"+Fib.fib2(10));
    }
}

class QuickSort {
    int[] arr;

    QuickSort(int[] arr) {
        this.arr = arr;
    }

    public void sort() {
        int left = 0, right = arr.length - 1;
        sort(left, right);
    }

    void sort(int left, int right) {
        if (left < right) {
            int c = part(left, right);
            sort(left, c - 1);
            sort(c + 1, right);
        }
    }

    int part(int left, int right) {
        int m = left;
        int i = m + 1;
        int index = i;
        while (i <= right) {
            if (arr[i] < arr[m]) {
                swap(index++, i);
            }
            i++;
        }
        int newM = index - 1;
        swap(m, newM);
        return newM;
    }

    void swap(int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

class MergeSort {
    int[] arr;
    int[] temp;

    MergeSort(int[] arr) {
        this.arr = arr;
        this.temp=new int[this.arr.length];
    }
    public void sort(){
        sort(0,arr.length-1);
    }

    void sort(int left, int right) {
        if (left < right) {
            int m = left + (right - left) / 2;
            sort(left, m);
            sort(m + 1, right);
            merge(left, m, right);
        }
    }

    void merge(int left, int m, int right) {
        int i=left;
        int j=m+1;
        int t=0;
        while (i <= m && j <= right) {
            if(arr[i]<arr[j]){
                temp[t++]=arr[i++];
            }else{
                temp[t++]=arr[j++];
            }
        }
        while (i<=m){
            temp[t++]=arr[i++];
        }
        while (j<=right){
            temp[t++]=arr[j++];
        }
        t=0;
        while (left<=right){
            arr[left++]=temp[t++];
        }

    }
}

class Fib{
    static public int fib(int n){
        if(n<2){
            return n;
        }
        int t=0,a=0,b=1;
        for(int i=2;i<=n;i++){
            t=a;
            a=b;
            b=t+a;
        }
        return b;
    }
    static public int fib2(int n){
        if(n<2)return n;
        return fib2(n-2)+fib2(n-1);
    }
}

class BubbleSort{
    static public void sort(int[] arr){
        for (int n=arr.length;n>-1;n--){
            for(int i=0;i<n-1;i++){
                if(arr[i]>arr[i+1]){
                    int t=arr[i+1];
                    arr[i+1]=arr[i];
                    arr[i]=t;
                }
            }
        }
    }
}